home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 196_01 / btree.c < prev    next >
Text File  |  1985-11-13  |  6KB  |  300 lines
  1. /* [BTREE.C of JUGPDS Vol.19]    */
  2.  
  3. /* B-Tree search, insertion and deletion
  4.    from ALGORITHMS+DATA STRUCTURES=PROGRAMS by N. Wirth
  5.    implemented for BDS C by H. Katayose (JUG-CP/M No.179) */
  6.  
  7. #define    NN    8
  8. #define    N    (NN/2)
  9. #define    PAGE    struct _page
  10. #define    ITEM    struct _item
  11. #define    NULL    0
  12. #define    TRUE    (-1)
  13. #define    FALSE    0
  14.  
  15. /*
  16.  * Storage allocation data, used by "alloc" and "free"
  17.  */
  18.  
  19. struct _header  {
  20.     struct _header *_ptr;
  21.     unsigned _size;
  22.  };
  23.  
  24. struct _header _base;        /* declare this external data to  */
  25. struct _header *_allocp;    /* be used by alloc() and free()  */
  26.  
  27.  
  28. struct    _item {
  29.     int    key;
  30.     PAGE    *right_ref;
  31.     int    count;
  32. };
  33.  
  34. struct    _page {
  35.     int    item_cnt;
  36.     PAGE    *left_ref;
  37.     ITEM    e[NN];
  38. };
  39.  
  40. PAGE    w;
  41.  
  42. main()
  43. {
  44.     int    i;
  45.     int    x, h;                /* h : boolean */
  46.     PAGE    *q, *root;
  47.     ITEM    u;
  48.  
  49.     root = NULL;
  50.     scanf("%d", &x);
  51.     while (x) {
  52.         printf("SEARCH KEY %d\n", x);
  53.         if (search(x, root, &u)) {
  54.             q = root;
  55.             new(&root);
  56.             root->item_cnt = 1;
  57.             root->left_ref = q;
  58.             itemcopy(root->e[0], u);
  59.         }
  60.         printtree(root, 0);
  61.         scanf("%d", &x);
  62.     }
  63.     scanf("%d", &x);
  64.     while (x) {
  65.         printf("DELETE KEY %d\n", x);
  66.         if (delete(x, root)) {
  67.             if (root->item_cnt == 0) {
  68.                 q = root;
  69.                 root = q->left_ref;
  70.             }
  71.         }
  72.         printtree(root, 0);
  73.         scanf("%d", &x);
  74.     }
  75. }
  76.  
  77.  
  78. search(x, a, v)
  79. PAGE    *a;
  80. ITEM    *v;
  81. {
  82.     int    i;
  83.     ITEM    u;
  84.  
  85.     if (a == NULL) {
  86.         v->key = x;
  87.         v->count = 1;
  88.         v->right_ref = NULL;
  89.         return TRUE;
  90.         }
  91.     for (i = 0; i < a->item_cnt && x > a->e[i].key; i++)
  92.         ;
  93.     if (x == a->e[i].key && i < a->item_cnt)
  94.         a->e[i].count++;
  95.     else
  96.         if (search(x, i ? a->e[i-1].right_ref : a->left_ref, &u))
  97.             return insert(a, i, &u, v);
  98.     return FALSE;
  99. }
  100.  
  101.  
  102. insert(a, i, u, v)
  103. PAGE    *a;
  104. ITEM    *u, *v;
  105. {
  106.     PAGE    *b;
  107.     int    j, h;
  108.  
  109.     if (a->item_cnt < NN) {
  110.         for (j = a->item_cnt++; j >= i+1; j--)
  111.             itemcopy(a->e[j], a->e[j-1]);
  112.         itemcopy(a->e[i], u);
  113.         return FALSE;
  114.     } else {            /* page a is full; split it and
  115.                        assign the emerging item to v */
  116.         new(&b);
  117.         if (i <= N) {
  118.             if (i == N)
  119.                 itemcopy(v, u);
  120.             else {
  121.                 itemcopy(v, a->e[N-1]);
  122.                 for (j = N-1; j >= i+1; j--)
  123.                     itemcopy(a->e[j], a->e[j-1]);
  124.                 itemcopy(a->e[i], u);
  125.             }
  126.             for (j = 0; j <= N-1; j++)
  127.                 itemcopy(b->e[j], a->e[j+N]);
  128.         } else {
  129.             i -= N;
  130.             itemcopy(v, a->e[N]);
  131.             for (j = 0; j <= i - 2; j++)
  132.                 itemcopy(b->e[j], a->e[j+N+1]);
  133.             itemcopy(b->e[i-1], u);
  134.             for (j = i; j <= N-1; j++)
  135.                 itemcopy(b->e[j], a->e[j+N]);
  136.         }
  137.         a->item_cnt = b->item_cnt = N;
  138.         b->left_ref = v->right_ref;
  139.         v->right_ref = b;
  140.     }
  141.     return TRUE;
  142. }
  143.  
  144.  
  145. itemcopy(d, s)
  146. ITEM    *d, *s;
  147. {
  148.     d->key = s->key;
  149.     d->right_ref = s->right_ref;
  150.     d->count = s->count;
  151. }
  152.  
  153.  
  154. new(p)
  155. PAGE    **p;
  156. {
  157.     PAGE    *alloc();
  158.  
  159.     if ((*p = alloc(sizeof **p)) == NULL)
  160.         exit();
  161. }
  162.  
  163.  
  164. printtree(p, l)
  165. PAGE    *p;
  166. {
  167.     int    i;
  168.  
  169.     if (p != NULL) {
  170.         for (i = 0; i <= l; i++)
  171.             printf("    ");
  172.         for (i = 0; i < p->item_cnt; i++)
  173.             printf("%4d", p->e[i].key);
  174.         putchar('\n');
  175.         printtree(p->left_ref, l+1);
  176.         for (i = 0; i < p->item_cnt; i++)
  177.             printtree(p->e[i].right_ref, l+1);
  178.     }
  179. }
  180.  
  181.  
  182. delete(x, a)
  183. PAGE *a;
  184. {
  185.     int    i;
  186.     int    k, l, r;
  187.     PAGE    *q;
  188.  
  189.     if (a == NULL) {
  190.         printf("Key is not in tree!\n");
  191.         return FALSE;
  192.     } else {                /* binary array search */
  193.         for (l = 0, r = a->item_cnt - 1; l <= r; ) {
  194.             k = (l + r)/2;
  195.             if (x <= a->e[k].key) r = k-1;
  196.             if (x >= a->e[k].key) l = k+1;
  197.         }
  198.         q = (r == -1) ? a->left_ref : a->e[r].right_ref;
  199.         if (l - r > 1)            /* found, now delete e[k] */
  200.             if (q == NULL) {    /* a is a terminal page   */
  201.                 a->item_cnt--;
  202.                 for (i = k; i < a->item_cnt; i++)
  203.                     itemcopy(a->e[i], a->e[i+1]);
  204.                 return (a->item_cnt < N);
  205.                 }
  206.             else {
  207.                 if (del(q, a, k))
  208.                     return underflow(a, q, r);
  209.                 }
  210.         else {
  211.             if (delete(x, q))
  212.                 return underflow(a, q, r);
  213.             }
  214.         }
  215. }
  216.  
  217.  
  218. underflow(c, a, s)
  219. PAGE    *c, *a;
  220. int    s;
  221. {
  222.     PAGE *b;
  223.     int i, k, mb, mc;
  224.  
  225.     mc = c->item_cnt;        /* h : true, a->item_cnt = n - 1 */
  226.     if (s < mc-1) {
  227.         s++;
  228.         b = c->e[s].right_ref;
  229.         mb = b->item_cnt;
  230.         k = (mb - N + 1)/2;
  231.         itemcopy(a->e[N-1], c->e[s]);
  232.         a->e[N-1].right_ref = b->left_ref;
  233.         if (k > 0) {
  234.             for(i = 0; i < k-1; i++)
  235.                 itemcopy(a->e[i+N], b->e[i]);
  236.             itemcopy(c->e[s], b->e[k-1]);
  237.             c->e[s].right_ref = b;
  238.             b->left_ref = b->e[k-1].right_ref;
  239.             mb -= k;
  240.             for (i = 0; i < mb; i++)
  241.                 itemcopy(b->e[i],b->e[i+k]);
  242.             b->item_cnt = mb;
  243.             a->item_cnt = N-1+k;
  244.             return FALSE;
  245.             }
  246.         else {
  247.             for (i = 0; i <  N; i++) itemcopy(a->e[i+N], b->e[i]);
  248.             for (i = s; i < mc; i++) itemcopy(c->e[i], c->e[i+1]);
  249.             a->item_cnt = NN;
  250.             c->item_cnt = mc-1;
  251.             }
  252.         }
  253.     else {
  254.         b = (s == 0) ? c->left_ref : c->e[s-1].right_ref;
  255.         mb = b->item_cnt + 1;
  256.         k = (mb - N) / 2;
  257.         if (k > 0) {
  258.             for(i = N-2; i >= 0; i--)
  259.                 itemcopy(a->e[i+k], a->e[i]);
  260.             itemcopy(a->e[k-1], c->e[s]);
  261.             a->e[k-1].right_ref = a->left_ref;
  262.             mb -= k;
  263.             for (i = k-2; i>=0; i--) itemcopy(a->e[i], b->e[i+mb]);
  264.             a->left_ref = b->e[mb].right_ref;
  265.             itemcopy(c->e[s], b->e[mb-1]);
  266.             c->e[s].right_ref = a;
  267.             b->item_cnt = mb - 1;
  268.             a->item_cnt = N-1+k;
  269.             return FALSE;
  270.             }
  271.         else {
  272.             itemcopy(b->e[mb], c->e[s]);
  273.             b->e[mb].right_ref = a->left_ref;
  274.             for (i = 0; i < N-1; i++)
  275.                 itemcopy(b->e[i+mb], a->e[i]);
  276.             b->item_cnt = NN;
  277.             c->item_cnt = mc-1;
  278.             }
  279.     }
  280.     return TRUE;
  281. }
  282.  
  283.  
  284. del(p, a, k)
  285. PAGE    *p, *a;
  286. {
  287.     PAGE    *q;
  288.  
  289.     if ((q = p->e[p->item_cnt-1].right_ref) != NULL) {
  290.         if (del(q, a, k))
  291.             return underflow(p, q, p->item_cnt-1);
  292.         }
  293.     else {
  294.         p->e[p->item_cnt-1].right_ref = a->e[k].right_ref;
  295.         itemcopy(a->e[k], p->e[p->item_cnt-1]);
  296.         p->item_cnt--;
  297.         return (p->item_cnt < N);
  298.     }
  299. }
  300.